#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<string.h>
#include<vector>
class Solution {
public:
    int maximumSwap(int num) {
        vector<int> nums(8, 0);
        vector<int> si(10, 0);
        int k = 0;
        while (num)
        {
            int temp = num % 10;
            nums[k++] = temp;
            si[temp]++;
            num /= 10;
        }
        int n = k;
        for (int i = 9; i >= 1; i--)
        {
            int flag = 0;
            while (si[i] && flag == 0)
            {
                if (nums[k - 1] < i)
                {
                    int temp = nums[k - 1];
                    for (int j = k - 1; k >= 0; j--)
                    {
                        if (nums[j] == i && si[i] == 1)
                        {
                            flag = 1;
                            nums[j] = temp;
                            nums[k - 1] = i;
                            break;
                        }
                        else if (nums[j] == i && si[i] != 1)
                        {
                            si[i]--;
                        }
                    }
                }
                else
                {
                    si[i]--;
                    k--;
                }
            }
            if (flag == 1)
            {
                break;
            }
        }
        int sum = 0;
        for (int i = n - 1; i >= 0; i--)
        {
            sum = sum * 10 + nums[i];
        }
        return sum;
    }
};


int main()
{
    
    return 0;
}
